package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 剑指 Offer 06. 从尾到头打印链表
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：head = [1,3,2]
 * 输出：[2,3,1]
 *  
 *
 * 限制：
 *
 * 0 <= 链表长度 <= 10000
 *
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dt66m/
 * @author SHM
 */
public class ReversePrint {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
//        int len = 0;
        ListNode tmp = head;
        while(tmp!=null){
//            len++;
            stack.push(tmp);
            tmp = tmp.next;
        }
        int len = stack.size();
        int[] ans= new int[len];
        int i=0;
        while(!stack.isEmpty()){
            ans[i] = stack.pop().val;
            i++;
        }
//        for (int i = 0; i < len; i++) {
//            ans[i] = stack.pop().val;
//        }

        return ans;
    }

    ArrayList<Integer> tmp = new ArrayList<Integer>();

    /**
     * 方法一：递归法
     * 利用递归，先递推至链表末端；回溯时，依次将节点值加入列表，即可实现链表值的倒序输出。
     *
     * 递归解析：
     * 终止条件： 当 head == None 时，代表越过了链表尾节点，则返回空列表；
     * 递推工作： 访问下一节点 head.next ；
     * 回溯阶段：
     * Python： 返回 当前 list + 当前节点值 [head.val] ；
     * Java / C++： 将当前节点值 head.val 加入列表 tmp ；
     * 复杂度分析：
     * 时间复杂度 O(N)O(N)： 遍历链表，递归 NN 次。
     * 空间复杂度 O(N)O(N)： 系统递归需要使用 O(N)O(N) 的栈空间。
     *
     * 作者：Krahets
     * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5d8831/
     * @param head
     * @return
     */
    public int[] reversePrint_2(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }
    void recur(ListNode head) {
        if(head == null) {
            return;
        }
        recur(head.next);
        tmp.add(head.val);
    }

//    作者：Krahets
//    链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5d8831/

    /**
     * 找到长度
     * 再查一遍给出结果
     * @param head
     * @return
     */
    public int[] reversePrint_3(ListNode head) {
        ListNode tmp = head;
        int len = 0;
        while(tmp!=null){
            ++len;
            tmp = tmp.next;
        }

        int[] res = new int[len];
        tmp = head;
        int index = len-1;
        while(tmp!=null){
            res[index--] = tmp.val;
            tmp = tmp.next;
        }
        return res;
    }
}
